/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/intersection-of-two-linked-lists
   @Language: C++
   @Datetime: 16-02-09 05:54
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	/**
	 * @param headA: the first list
	 * @param headB: the second list
	 * @return: a ListNode
	 */
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		// write your code here
		int la=0, lb=0;
		ListNode *p, *q;
		for(p=headA; p; p=p->next,++la);
		for(p=headB; p; p=p->next,++lb);
		for(p=headA; la>lb; p=p->next,--la);
		for(q=headB; lb>la; q=q->next,--lb);
		for(; p!=q; p=p->next,q=q->next);
		return p;
	}
};
